using System.Linq;
using NUnit.Framework;

namespace Solver
{
	/// <summary>
	/// Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
	/// </summary>
	public class Problem023 : SelfChecker, IProblem
	{
		private static readonly int[] Primes500 = new[]
		{
			2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
			101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 
			211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 
			307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 
			401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499
		};

		public int Id
		{
			get { return 23; }
		}

		public string Solve()
		{
			var abundants = GetAbundants();
			var numFlags = new bool[20161];
			foreach (var n1 in abundants)
				foreach (var n2 in abundants)
					if (n1 + n2 < numFlags.Length)
						numFlags[n1 + n2] = true;
			return (numFlags.Select((b, idx) => b ? 0 : (long)idx).Sum() + 20161).ToString();
		}

		private static int[] GetAbundants()
		{
			return Enumerable.Range(0, 20161)
				.Select(n => new { n, s = n.SumOfDivisors(Primes500) })
				.Where(p => p.s > p.n)
				.Select(p => p.n)
				.ToArray();
		}

		[Test]
		public override void Check()
		{
			Assert.AreEqual("4179871", Solve());
		}
	}
}